package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 12/23/20 2:44 PM
 *
 *  https://leetcode-cn.com/problems/insertion-sort-list/
 */
public class _147_对链表进行插入排序 {

    public ListNode insertionSortList(ListNode head) {

        if (head == null) {

            return head;
        }

        ListNode root = new ListNode(Integer.MIN_VALUE);
        root.next = head;
        ListNode node = head;
        ListNode pre = root;
        /**
         * 从 node.next 这个节点开始排序
         */
        while (node != null) {

            if (node.val > pre.val) {

                pre = node;
                node = node.next;
                continue;
            }

            ListNode fNode;
            if (root.next.val > node.val) {

                fNode = root;
            }else {
                fNode = findNode(root, node);

            }

            if (fNode != null) {

                ListNode tmpNode = fNode.next;
                ListNode tmpNext = node.next;

                fNode.next = node;
                node.next = tmpNode;
                pre.next = tmpNext;

                node = tmpNext;
            }else {

                pre = node;
                node = node.next;
            }

        }

        return root.next;
    }

    private ListNode findNode(ListNode root,ListNode endNode) {

        ListNode node = root;
        ListNode preNode = null;

        while (node != endNode) {

            if (endNode.val < node.val) {

                break;
            }
            preNode = node;
            node = node.next;
        }

        return  node == endNode ? null:preNode;
    }

    public static void main(String[] args) {

        // 插入排序

        int[] nums = new int[]{7,3,4,3,5,1,2,6};

        // 1,2,2,4,2,1
        for (int i = 1; i < nums.length; i++) {

            int index = findFirstLarge(nums, i);

            if (index == i) {
                continue;
            }

            int num = nums[i];

            for (int j = i - 1; j >= index; j--) {

                nums[j+1] = nums[j];
            }
            nums[index] = num;
        }

        System.out.println(Arrays.toString(nums));
    }

    private static int findFirstLarge(int[] nums, int i1) {

        int num = nums[i1];
        int left = 0, right = i1 - 1, mid;

        while (left <= right) {

            /**
             * 注意点
             * 一. 这里不要使用 (left + right) >> 1 , left + right 有可能int越界
             *
             * 二. 关于right开闭选择
             * 1. 如果取值范围为 [left,right],
             *      奇数个元素时: mid 为中心点元素
             *      偶数个元素时: mid 为上中心点元素
             *
             * 2. 如果取值范围为 [left,right),
             *       奇数个元素时: mid 为中心点元素
             *       偶数个元素时: mid 为下中心点元素
             */
            mid = left + ((right - left) >> 1);

            if (num >= nums[mid]) {

                left = mid + 1;
            }else {

                right = mid;

                if (left == right) {

                    break;
                }
            }
        }

        /**
         * left == right 时，说明left当前位置的元素大于 num
         * left == right + 1 时，说明 在 0-i1 之间没有 大于num的值
         */
        return left;
    }
}
